#常规非递归
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        stack = []
        output = []
        top = root
        while len(stack) > 0 or top:
            while top:
                stack.append(top)
                top = top.left
            top = stack.pop()
            output.append(top.val)
            top = top.right

        return output

#今天新接触了一个方法，很受启发。因为数据类型分为TreeNode，和它的值int两种，通过向栈放入不同的数据类型来达到判断是否访问过的作用
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack,rst=[root],[]
        while stack:
            i=stack.pop()
            if isinstance(i,TreeNode):
                #这一步是核心，注意放入栈的顺序，从栈顶到栈底。相当于一个“剥壳”的过程
                stack.extend([i.right,i.val,i.left])
            elif isinstance(i,int):
                rst.append(i)
        return rst